#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int ElemSet; /* 默认元素键值为整型 */
#define kMaxSize 3    /* RAM中数据数组的最大规模 */
typedef struct RecordNode *Records;
struct RecordNode {
    ElemSet key; /* 关键字 */
    /* 其他属性由用户自定义 */
};

void CopyRecord(Records source, Records destination) {
    /* 将记录source的内容复制到记录destination */
    destination->key = source->key;
    /* 复制其它属性 */
}

/* 二叉堆定义及操作 */
typedef Records HElemSet;
typedef int Position; /* 数组下标即为元素位置 */
typedef struct BinaryHeapNode *MinHeap;
struct BinaryHeapNode {
    HElemSet *data; /* 数据元素数组 */
    int size; /* 规模 */
    int capacity; /* 容量 */
};

void SiftDown(MinHeap h, Position i) {
    Position last, child;
    HElemSet elem;

    last = h->size - 1; /* 这是最后一个元素的位置 */
    elem = h->data[i];
    while (1) {
        child = (i << 1) + 1; /* child当前是i的左孩子的位置 */
        if (child < last
                && h->data[child + 1]->key < h->data[child]->key) { /* 如果i有右孩子并且右孩子更小 */
            child++; /* child更新为i的右孩子的位置 */
        } else if (child > last) { /* 如果i是叶子结点 */
            break; /* 已经调整到底，跳出循环 */
        }
        if (elem->key > h->data[child]->key) { /* 若较小的孩子比elem小 */
            h->data[i] = h->data[child]; /* 将较小的孩子结点上移 */
            i = child; /* i指向原结点的孩子结点，即向下调整 */
        } else { /* 若所有孩子都不比elem小 */
            break; /* 则找到了elem的最终位置，跳出循环 */
        }
    }
    h->data[i] = elem;
}

void MakeHeapDown(MinHeap h) {
    /* 快速建堆 */
    Position last;
    int i;

    last = h->size - 1; /* 这是最后一个元素的位置 */
    for (i = (last - 1) >> 1; i >= 0; i--) {
        SiftDown(h, i); /* 自底向上调整 */
    }
}
/* 二叉堆定义及操作结束 */

/* 缓冲区定义及操作 */
#define kMaxBuff 4    /* 缓冲区最大容量 */
#define EndCode (-1e9)  /* 表示空数据的键值，若按增序则定义为极小值 */
typedef int Position; /* 数组下标为数据位置 */
typedef struct BufferNode *Buffers;
struct BufferNode {
    Records b[kMaxBuff]; /* 缓冲区数据数组 */
    Position front; /* 前端位置 */
    Position rear; /* 后端位置 */
    int capacity; /* 总容量 */
};

Buffers InitBuffer() {
    /* 创建一块缓冲区 */
    Buffers buff;
    int i;

    buff = (Buffers)malloc(sizeof(struct BufferNode));
    buff->capacity = kMaxBuff;
    for (i = 0; i < buff->capacity; i++) {
        buff->b[i] = (Records)malloc(sizeof(struct RecordNode));
    }
    buff->front = buff->rear = 0;

    return buff;
}

bool FillBuffer(Buffers buff, FILE *f) {
    /* 从f读入一块数据到buff */
    int i;

    buff->front = buff->rear = 0; /* 清空缓冲区 */
    if (fscanf(f, "%d", &buff->b[0]->key) == EOF) {
        return false; /* 如果一个数据都读不进，说明文件已空，返回读取失败标志 */
    } else {
        buff->rear++; /* 成功读取第一个数据 */
    }
    for (; buff->rear < buff->capacity; buff->rear++) {
        if (fscanf(f, "%d", &buff->b[buff->rear]->key) == EOF) {
            break; /* 一直读到文件结尾 */
        }
    }
    return true;
}

Buffers InitInputBuffer(FILE *file_in) {
    /* 初始化输入缓冲区，读入一部分数据 */
    Buffers buff;

    buff = InitBuffer();
    FillBuffer(buff, file_in);

    return buff;
}

Buffers InitOutputBuffer() {
    /* 初始化输出缓冲区 */
    Buffers buff;

    buff = InitBuffer();

    return buff;
}

void Flush(Buffers buff, FILE *f) {
    /* 将buff全部写入f */
    buff->front = 0;
    while (buff->front < buff->rear) {
        fprintf(f, "%d ", buff->b[buff->front]->key);
        buff->front++;
    }
    buff->front = buff->rear = 0; /* 清空缓冲区 */
}

bool IsEmpty(Buffers buff) {
    /* 判断buff是否为空 */
    return (buff->front == buff->rear);
}

bool IsFull(Buffers buff) {
    /* 判断buff是否为满 */
    return (buff->rear == buff->capacity);
}

void SendToOutputBuffer(Records rec, Buffers buff, FILE *f) {
    /* 将rec写到buff */
    if (IsFull(buff) == true) { /* 如果buff已满 */
        Flush(buff, f); /* 写到磁盘文件f */
    }
    CopyRecord(rec, buff->b[buff->rear]);
    buff->rear++;
}

Records Read(Buffers buff, FILE *f) {
    /* 从buff中读取一个数据 */
    Records rec;

    /* 如果当前buff为空，且文件也空了 */
    if ((IsEmpty(buff) == true) && (FillBuffer(buff, f) == false)) {
        buff->front = buff->rear = 0; /* 清空缓冲区 */
        buff->b[buff->front]->key = EndCode; /* 加结束标识 */
        rec = buff->b[buff->front];
    } else {
        rec = buff->b[buff->front];
        buff->front++;
    }

    return rec;
}

void EndUpOutputBuffer(MinHeap h, Buffers buff, FILE *f) {
    /* 将堆h中剩余的数据顺序输出到buff，最后写入磁盘文件f */
    MakeHeapDown(h); /* 建最小堆 */
    while (h->size > 0) { /* 堆不为空就重复循环 */
        if (h->data[0]->key != EndCode) { /* 将非空最小值写入buff */
            SendToOutputBuffer(h->data[0], buff, f);
        }
        CopyRecord(h->data[h->size - 1],
                   h->data[0]); /* 用最后元素代替根结点 */
        h->size--;
        if (h->size > 0) {
            SiftDown(h, 0); /* 重新排列堆，筛出根结点 */
        }
    } /* 结束最后一个顺串 */
    if (IsEmpty(buff) == false) {
        Flush(buff, f); /* 把输出缓冲区中剩余的数据写进磁盘文件 */
        fprintf(f, "\n"); /* 每个顺串的输出占一行 */
    }
}
/* 缓冲区定义及操作结束 */

void ReadToRam(FILE *file_in, int m, Records ram_array[]) {
    /* 从磁盘读m个记录放到数组ram_array中 */
    int i;

    for (i = 0; i < m; i++) {
        ram_array[i] = (Records)malloc(sizeof(struct RecordNode));
        fscanf(file_in, "%d", &ram_array[i]->key);
    }
}

/* 算法 13-5：置换选择算法 ReplacementSelection(ram_array, m, file_in, file_out) */
void ReplacementSelection(Records ram_array[], int m, FILE *file_in,
                          FILE *file_out) {
    MinHeap h;
    Records record, min_rec;
    Buffers buffer_in, buffer_out;

    ReadToRam(file_in, m,
              ram_array); /* 从磁盘读m个记录放到数组ram_array中 */
    /* 初始化一个最小堆，以ram_arry为数组，m为其规模 */
    h = (MinHeap)malloc(sizeof(struct BinaryHeapNode));
    h->capacity = h->size = m;
    h->data = ram_array;
    buffer_in = InitInputBuffer(
                    file_in); /* 初始化输入缓冲区，读入一部分数据 */
    buffer_out = InitOutputBuffer(); /* 初始化输出缓冲区 */
    while (1) {
        MakeHeapDown(h); /* 建最小堆 */
        while (h->size > 0) { /* 堆不为空就重复循环 */
            min_rec = h->data[0]; /* 堆的最小值 */
            SendToOutputBuffer(min_rec, buffer_out,
                               file_out); /* 把min_rec送到输出缓冲区 */
            record = Read(buffer_in,
                          file_in); /* 从输入缓冲区读入一个记录record */
            if (record->key >= min_rec->key) {
                CopyRecord(record, h->data[0]); /* 把record放到根结点 */
            } else {
                CopyRecord(h->data[h->size - 1],
                           h->data[0]); /* 否则用最后元素代替根结点 */
                CopyRecord(record, h->data[h->size -
                                           1]); /* 把record放到最后位置，下标为h.size-1 */
                h->size--;
            }
            if (h->size > 0) {
                SiftDown(h, 0); /* 重新排列堆，筛出根结点 */
            }
        }
        Flush(buffer_out,
              file_out); /* 算法结束一个顺串，把输出缓冲区中剩余的数据写进磁盘文件 */
        fprintf(file_out, "\n"); /* 每个顺串的输出占一行 */
        h->size = m; /* 准备将堆的数组重建一个新的最小堆 */
        if (h->data[0]->key == EndCode) { /* 如果此时根结点键值为空 */
            break; /* 意味着输入数据已经读完，跳出循环 */
        }
    }
    EndUpOutputBuffer(h, buffer_out, file_out); /* 将堆中剩余数据输出 */
    free(h);
    free(buffer_in);
    free(buffer_out);
}
/* 算法13-5 结束 */

int main(void) {
    FILE *file_in, *file_out;
    Records ram_array[kMaxSize];

    file_in = fopen("in.txt", "r");
    file_out = fopen("out.txt", "w");
    ReplacementSelection(ram_array, kMaxSize, file_in, file_out);
    fclose(file_in);
    fclose(file_out);

    return 0;
}